// @algorithm @lc id=54 lang=cpp 
// @title spiral-matrix


// @test([[1,2,3],[4,5,6],[7,8,9]])=[1,2,3,6,9,8,7,4,5]
// @test([[1,2,3,4],[5,6,7,8],[9,10,11,12]])=[1,2,3,4,8,12,11,10,9,5,6,7]
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;
        int left = 0, bottom = matrix.size(), // rows
            top = 0, right = matrix[0].size(); // cols
        while(true){
            // leftTop -> rightTop
            for(int i=left; i<right; i++)
                ans.push_back(matrix[top][i]);
            if(++top >= bottom) break;
            // rightTop -> rightBottom
            for(int i=top; i<bottom; i++)
                ans.push_back(matrix[i][right-1]);
            if(--right <= left) break;
            // rightBottom -> leftBottom
            for(int i=right-1; i>=left; i--)
                ans.push_back(matrix[bottom-1][i]);
            if(--bottom <= top) break;
            // leftBottom -> leftTop
            for(int i=bottom-1; i>=top; i--)
                ans.push_back(matrix[i][left]);
            if(++left >= right) break;
        }
        return ans;
    }
};